package recursive.KthGrammar;
/**
 * @Date 2020/04/02
 * @author 王光浩 
 * @Thinking 使用递归实现，我们可以发现第k个元素值，等于上一层的K-上一层元素总个数位置处的值，取反。
 * @Analysis 时间复杂度O（N），空间复杂度O（N）
 */
public class MyMethodFive {
	public int kthGrammar(int N, int K) {
		if(N==1)return 0;
		int pow=(int)Math.pow(2, N-2);
		if(K>pow) return kthGrammar(N-1,K-pow)^1;
		else return kthGrammar(N-1,K);
    }
}
